#include "../head/myhead.h"

/**
 * 3.给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。岛屿:相邻陆地可以组成一个岛屿(相邻:上下左右)判断岛屿个数。
 * 例如: 输入：
 *      1 1 0 0 0
 *      0 1 0 1 1
 *      0 0 0 1 1
 *      0 0 0 0 0
 *      0 0 1 1 1
 * 思路：统计1的堆数即可，定义一个全局变量sum，每次遇到1就sum++，并且将1变为0，同时使用深度优先搜索将该1的上下左右都变为0
 */
void dfs(int grid[][MAXSIZE], int x, int y, int m, int n)
{
    // x,y为二维数组grid下标
    if (x < 0 || x > m || y < 0 || y > n)
        return; // 超出grid边界
    grid[x][y] = 0;
    dfs(grid, x, y - 1, m, n); //
    dfs(grid, x, y + 1, m, n);
    dfs(grid, x - 1, y, m, n);
    dfs(grid, x + 1, y, m, n);
}
// m为矩阵行数，n为列数
int solve(int grid[][MAXSIZE], int m, int n)
{
    int sum = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 1)
            {
                sum++;
                dfs(grid, i, j, m, n);
            }
        }
    }
    return sum;
}